package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/linked-list-cycle-ii/">环形链表II [中等]</a>
 * 需要将环形链表相对于head起始位置的地址返回，如果没有环形链表返回null
 *
 * @author zhenzicheng
 * @date: 2022-06-02 10:06
 * @see LinkedListCycle_141
 */
public class LinkedListCycleII_142 {

  public ListNode detectCycle(ListNode head) {
    if (head == null) {
      return null;
    }

    ListNode fast = head, slow = head;
    boolean isCycle = false;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) {
        isCycle = true;
        break;
      }
    }
    if (isCycle) {
      slow = head; // 将慢指针指向头，重新开始遍历
      while (slow != fast) {
        slow = slow.next;
        fast = fast.next; // 重新遍历时快指针速度与慢指针都移动一位
      }
      return slow;
    }
    return null;
  }
}
